package Ruanj1;

import java.util.Arrays;

public class MaxArray {
    public static void main(String[] args) {
        int[] arr = {-1,5,6,-3,1,9,0,-6};
        SubarrayResult result = maxSubArr(arr);
        System.out.println("最大子数组和: " + result.maxSum);
        System.out.println("最大子数组: " + Arrays.toString(result.subarray));
    }

    // 用于存储结果的内部类
    static class SubarrayResult {
        int maxSum;      // 最大和
        int[] subarray;  // 最大子数组


        public SubarrayResult(int maxSum, int[] subarray) {
            this.maxSum = maxSum;
            this.subarray = subarray;
        }
    }

    public static SubarrayResult maxSubArr(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new SubarrayResult(0, new int[0]);
        }
        int max = nums[0];
        int curMax = nums[0];

        // 用于追踪子数组的索引
        int start = 0;            // 全局最大子数组的起始索引
        int end = 0;              // 全局最大子数组的结束索引
        int tempStart = 0;        // 当前子数组的起始索引

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > curMax + nums[i]) {
                // 重新开始新的子数组
                curMax = nums[i];
                tempStart = i;    // 更新当前子数组的起始位置
            } else {
                // 延续前面的子数组
                curMax = curMax + nums[i];
            }
            // 到目前为止找到的最大子数组和及对应的索引
            if (curMax > max) {
                max = curMax;
                start = tempStart;
                end = i;
            }
        }
        // 提取最大子数组
        int[] maxSubarray = new int[end - start + 1];
        for (int i = start, j = 0; i <= end; i++, j++) {
            maxSubarray[j] = nums[i];
        }
        return new SubarrayResult (max, maxSubarray);
    }

}
